home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 8: LINUX Games / Linux Cubed Series 8 - LINUX Games.iso / games / muds / pennmush.000 / pennmush-1.50-p8-linux.tar / pennmush / smalloc.c < prev    next >
C/C++ Source or Header  |  1991-10-04  |  15KB  |  672 lines
  1. #ifdef USE_SMALLOC
  2. /*
  3.  
  4.         Satoria's Malloc Package 1.2
  5. */
  6.  
  7. #include <stdio.h>
  8. #include <memory.h>
  9. #include "config.h"
  10. #include "externs.h"
  11.  
  12. #define MTYPE unsigned int
  13.  
  14. #define SMALL_BLOCK_MAX_BYTES    32
  15. #define SMALL_CHUNK_SIZE    0x4000
  16. #define CHUNK_SIZE        0x40000
  17.  
  18. #define SINT sizeof(int)
  19. #define SMALL_BLOCK_MAX (SMALL_BLOCK_MAX_BYTES/SINT)
  20.  
  21. #define PREV_BLOCK    0x80000000
  22. #define THIS_BLOCK    0x40000000
  23. #define MASK        0x0FFFFFFF
  24.  
  25. typedef unsigned int u;
  26.  
  27. /*
  28.     SMALL BLOCK data structures
  29. */
  30.  
  31. static u *sfltable[SMALL_BLOCK_MAX];    /* freed list */
  32. static u *next_unused;
  33. static u unused_size;            /* until we need a new chunk */
  34.  
  35. /*
  36.     LARGE BLOCK data structures
  37. */
  38.  
  39. static u *free_list;
  40. static u *start_next_block;
  41.  
  42. /*
  43.     STATISTICS
  44. */
  45.  
  46. static int small_count[SMALL_BLOCK_MAX];
  47. static int small_total[SMALL_BLOCK_MAX];
  48.  
  49. typedef struct { unsigned counter; unsigned long size; } stat;
  50.  
  51. #ifndef SLOW_STATISTICS
  52. #define COUNT(a,b)
  53. #define START(a)
  54. #else
  55. #define COUNT(a,b)             \
  56.     {                \
  57.         a.size+=(b);        \
  58.         if ((b)<0)        \
  59.             --a.counter;    \
  60.         else            \
  61.             ++a.counter;    \
  62.     }
  63. #define START(a) a.size=0; a.counter=0;
  64. #endif
  65.  
  66. #ifdef DEBUG
  67. int debugmalloc = 1;    /* Only used when debuging malloc() */
  68. #else
  69. int debugmalloc = 0;
  70. #endif
  71.  
  72. /********************************************************/
  73. /*  SMALL BLOCK HANDLER                    */
  74. /********************************************************/
  75.  
  76. char *large_malloc();
  77. static void large_free();
  78.  
  79. #define ptr_to_smallblock_size_field(p)    (p)
  80. #define next_free_smallblock(p)    ((u **) (p+1))
  81.  
  82. stat    small_alloc_stat,        /* amount allocated */
  83.     small_free_stat,        /* amount unused */
  84.     small_total_stat,        /* total ever requested */
  85.     small_chunk_stat;        /* small chunks allocated */
  86.  
  87. void *malloc(sz)
  88. MTYPE sz;
  89. {
  90.     u *temp,i,size;
  91.  
  92.     if (sz == 0) {
  93.         fprintf(stderr, "Malloc size 0.\n");
  94.         return NULL;
  95.     }
  96.  
  97.     if (sz>SMALL_BLOCK_MAX_BYTES)
  98.         return large_malloc((u) sz,0);
  99.  
  100. /* Compute the index into the small block table:
  101.     index        block size
  102.       0          1-4 bytes
  103.       1          5-8 bytes
  104.       2          9-12 bytes
  105. */
  106.  
  107.     i = (sz - 1) >> 2;
  108.  
  109. /* Compute the actual size of the small block in ints,
  110.    including the one int overhead for the "header"
  111. */
  112.  
  113.     size = (sz + 3) >> 2;            /* block size in ints */
  114.     ++size;                    /* one int overhead */
  115.  
  116. /* Update statistics of small block allocations */
  117.  
  118.     COUNT(small_alloc_stat,size << 2);
  119.     COUNT(small_total_stat,size << 2);
  120.  
  121.     small_count[i] += 1;            /* update statistics */
  122.     small_total[i] += 1;
  123.  
  124. /* Is the free list for this size of block non-empty? */
  125.  
  126.     if (sfltable[i]) {
  127.  
  128. /* Update the free list stats */
  129.  
  130.         COUNT(small_free_stat, -(int) (size << 2));
  131.  
  132.         temp = sfltable[i];
  133.         sfltable[i] = * (u **) (temp+1);
  134.  
  135.         return (char *) (temp+1);
  136.     }
  137.  
  138. /* Free list was empty.  So allocate from the small-block chunk. */
  139.  
  140.     if (unused_size<size) {
  141.  
  142. /* There's not enough room in this chunk.  Blow it off (wasting the
  143.    space at the end of the chunk), and get a new one. */
  144.  
  145.         next_unused = (u *) large_malloc(SMALL_CHUNK_SIZE,1);
  146.         if (next_unused == 0)
  147.             return 0;
  148.  
  149.         COUNT(small_chunk_stat, SMALL_CHUNK_SIZE+SINT);
  150.         unused_size = SMALL_CHUNK_SIZE / SINT;
  151.     }
  152.  
  153.     temp = (u *) next_free_smallblock(next_unused);
  154.  
  155.     *ptr_to_smallblock_size_field(next_unused) = size;
  156.     next_unused += size;
  157.     unused_size -= size;
  158.  
  159.     return (char *) temp;
  160. }
  161.  
  162. void free(ptr)
  163. char *ptr;
  164. {
  165.     u *block;
  166.     u i;
  167.  
  168. /* Find the header for this block */
  169.  
  170.     block = (u *) ptr;
  171.     block -= 1;
  172.  
  173. /* Test the size of this block to see if it's large or small */
  174.  
  175.     if ( (*ptr_to_smallblock_size_field(block) & MASK)
  176.          > SMALL_BLOCK_MAX + 1) {
  177.             large_free(ptr);
  178.             return;
  179.     }
  180.  
  181. /* Get index for this size of block.  There's no & MASK because
  182.    small block headers only have the size
  183. */
  184.     i = *block - 2;
  185.  
  186. /* Update the statistics */
  187.  
  188.     COUNT(small_alloc_stat, - (int) ((i+2) << 2));
  189.     COUNT(small_free_stat, (i+2) << 2);
  190.  
  191.     small_count[i] -= 1;
  192.  
  193.     *next_free_smallblock(block) = sfltable[i];
  194.     sfltable[i] = block;
  195. }
  196.  
  197. /************************************************/
  198. /*    LARGE BLOCK HANDLER            */
  199. /************************************************/
  200.  
  201. #define BEST_FIT    0
  202. #define FIRST_FIT    1
  203. #define HYBRID        2
  204. int fit_style = BEST_FIT;
  205.  
  206. #define ptr_to_largeblock_size_field(p)            (p)
  207. #define next_free_largeblock(p)                (*((u **) (p+1)))
  208. #define previous_free_largeblock(p)            (*((u **) (p+2)))
  209. #define next_large_block(p)                (p + (*(p) & MASK))
  210. #define previous_largeblock(p)                 (p - (*(p-1)))
  211. #define is_previous_free(p)                (!(*p & PREV_BLOCK))
  212. #define is_next_free(p)            (!(*next_large_block(p) & THIS_BLOCK))
  213.  
  214. #ifdef DEBUG
  215. static void show_block(ptr)
  216. u *ptr;
  217. {
  218.     fprintf(stderr, "MALLOC: [%c%d: %d]\n",(*ptr & THIS_BLOCK ? '+' : '-'),
  219.         (int) ptr, *ptr & MASK);
  220. }
  221.  
  222. void show_free_list()
  223. {
  224.     u *p;
  225.     p = free_list;
  226.     while (p) {
  227.         show_block(p);
  228.         p = next_free_largeblock(p);
  229.     }
  230. }
  231. #endif
  232.  
  233. stat large_free_stat;
  234. stat large_free_chain;
  235.  
  236. void remove_from_free_list(ptr)
  237. u *ptr;
  238. {
  239.     COUNT(large_free_stat, - (int) ((*ptr & MASK) << 2));
  240.  
  241.     if (previous_free_largeblock(ptr))
  242.         next_free_largeblock(previous_free_largeblock(ptr))
  243.             = next_free_largeblock(ptr);
  244.     else
  245.         free_list
  246.             = next_free_largeblock(ptr);
  247.  
  248.     if (next_free_largeblock(ptr))
  249.         previous_free_largeblock(next_free_largeblock(ptr))
  250.             = previous_free_largeblock(ptr);
  251. }
  252.  
  253. void add_to_free_list(ptr)
  254. u *ptr;
  255. {
  256.     COUNT(large_free_stat, (*ptr & MASK) << 2);
  257.  
  258.     if (free_list && previous_free_largeblock(free_list))
  259.         fprintf(stderr, "ERROR: Free list consistency error.\n");
  260.  
  261.     next_free_largeblock(ptr) = free_list;
  262.     if (free_list)
  263.         previous_free_largeblock(free_list) = ptr;
  264.     previous_free_largeblock(ptr) = 0;
  265.     free_list = ptr;
  266. }
  267.  
  268. /* build a properly annotated unallocated block */
  269. static void build_block(ptr, size)
  270. u *ptr,size;
  271. {
  272.  
  273. /* Set the header to:  (old value of PREV_BLOCK) | !THIS_BLOCK | size */
  274.  
  275.     *(ptr) = (*ptr & PREV_BLOCK) | size;
  276.  
  277. /* Set the footer (immediately before the next blocks' header) to the size */
  278.  
  279.     *(ptr+size-1) = size;
  280.  
  281. /* Clear PREV_BLOCK on the next block */
  282.  
  283.     *(ptr+size) &= (MASK | THIS_BLOCK);
  284. }
  285.  
  286. static void mark_block(ptr)
  287. u *ptr;
  288. {
  289.     *ptr |= THIS_BLOCK;
  290.     *next_large_block(ptr) |= PREV_BLOCK;
  291. }
  292.  
  293.  
  294. /*
  295.     mod by Lars Pensj| (??):
  296.         It is system dependent how sbrk() aligns data, so we simply
  297.         use brk() to insure that we have enough.
  298. */
  299. stat sbrk_stat;
  300. static char *esbrk(size)
  301. u size;
  302. {
  303.     extern char *sbrk();
  304.     extern int brk();
  305.     static char *current_break;
  306.  
  307.     if (current_break == 0)
  308.         current_break = sbrk(0);
  309.     if (brk(current_break + size) == -1)
  310.         return 0;
  311.     COUNT(sbrk_stat,size);
  312.     current_break += size;
  313.     return current_break - size;
  314. }
  315.  
  316. stat large_alloc_stat;
  317. stat large_total_stat;
  318. char *large_malloc(size, force_more)
  319. u size;
  320. int force_more;
  321. {
  322.     u best_size, real_size;
  323.     u *first, *best, *ptr;
  324.  
  325. /* Round the block size up to a multiple of 4, then divide by four, and add
  326.    1, to get the actual block size in ints, including room for the header
  327. */
  328.     size = (size + 7) >> 2;
  329.  
  330.     first = best = 0;
  331.     best_size = MASK;
  332.  
  333. /* If we are being forced to allocate a big block, ignore the fit attempts */
  334.  
  335.     if (force_more)
  336.         ptr = 0;
  337.     else {
  338.         ptr = free_list;
  339. #ifdef SLOW_STATISTICS
  340.         large_free_chain.counter++;
  341. #endif
  342.     }
  343.  
  344. /* run through the free list, looking for a perfect, first, or best fit */
  345.  
  346.     while (ptr) {
  347.         u tempsize;
  348. #ifdef SLOW_STATISTICS
  349.         large_free_chain.size++;
  350. #endif
  351.                         /* Perfect fit? */
  352.         tempsize = *ptr & MASK;
  353.         if (tempsize == size) {
  354.             best = first = ptr;
  355.             break;        /* always accept perfect fit */
  356.         }
  357.  
  358. /* If allocating this block for this malloc call would result in a hole
  359.    that's smaller than the minimum large block size, that is, smaller
  360.    than than SMALL_BLOCK_MAX, then it'd never get allocated.  So refuse
  361.    those cases.
  362. */
  363. #ifndef WASTE_SMALL
  364.         if (tempsize >= size + SMALL_BLOCK_MAX + 1) {
  365. #else
  366.         if (tempsize >= size) {
  367. #endif
  368.             if (!first) {
  369.                 first = ptr;
  370.                 if (fit_style == FIRST_FIT)
  371. /* If we're using first fit, just take this one! */
  372.                     break;
  373.             }
  374.  
  375. /* Find out how well this one fits */
  376.  
  377.             tempsize -= size;
  378.             if (tempsize>0 && tempsize<=best_size) {
  379.                 best = ptr;
  380.                 best_size = tempsize;
  381.             }
  382.         }
  383.  
  384.         ptr = next_free_largeblock(ptr);
  385.  
  386.     } /* end while */
  387.  
  388.     if (fit_style==BEST_FIT)
  389.         ptr = best;
  390.     else
  391.         ptr = first;    /* Hybrid says use first if no perfect */
  392.  
  393.     if (!ptr) {
  394.  
  395. /* There was no match, or we're forced, so allocate more memory */
  396.  
  397.         u chunk_size, block_size;
  398.  
  399.         block_size = size*SINT;
  400.  
  401.         if (force_more || (block_size>CHUNK_SIZE))
  402.             chunk_size = block_size;
  403.         else
  404.             chunk_size = CHUNK_SIZE;
  405.  
  406.         if (!start_next_block) {
  407.  
  408. /* This is the first allocation */
  409.  
  410.             start_next_block = (u *) esbrk(SINT);
  411.             if (!start_next_block)
  412.                 return 0;
  413.  
  414. /* The first block header must mark the previous block as used */
  415.  
  416.             *(start_next_block) = PREV_BLOCK;
  417.  
  418. /* Initialize statistics */
  419.  
  420.             START(large_alloc_stat)
  421.             START(large_total_stat)
  422.             START(large_free_stat)
  423.             START(sbrk_stat)
  424.             START(small_alloc_stat)
  425.             START(small_free_stat)
  426.             START(small_total_stat)
  427.             START(small_chunk_stat)
  428.             START(large_free_chain)
  429.         }
  430.  
  431.         ptr = (u *) esbrk(chunk_size);
  432.         if (ptr == 0)
  433.             return 0;
  434.  
  435. /* Old block at end of memory had an extra trailing word. Overwrite it. */
  436.  
  437.         ptr -= 1;
  438.  
  439.         block_size = chunk_size / SINT;
  440.  
  441. /* Configure the header information for this new bit. */
  442.  
  443.         build_block(ptr,block_size);
  444.  
  445. /* Set up the bogus header at the end of memory */
  446.  
  447.         *next_large_block(ptr)=THIS_BLOCK;
  448.  
  449. /* Stick this new block in the free list, so it's exactly like a real
  450.    free block, so it looks the same as one found in the free list
  451. */
  452.         add_to_free_list(ptr);
  453.     }
  454.  
  455. /* Ok, we got the free block of appropriate size from somewhere */
  456.  
  457.     remove_from_free_list(ptr);
  458.     real_size = *ptr & MASK;
  459.  
  460.     if (real_size != size) {
  461.         /* split block pointed to by ptr into two blocks */
  462.         build_block(ptr+size, real_size-size);
  463.         add_to_free_list(ptr+size);
  464.         build_block(ptr, size);
  465.     }
  466.  
  467.     mark_block(ptr);
  468.  
  469. /* Update statistics */
  470.  
  471.     COUNT(large_alloc_stat, size << 2);
  472.     COUNT(large_total_stat, size << 2);
  473.  
  474.     return (char *) (ptr + 1);
  475. }
  476.  
  477. static void large_free(ptr)
  478. char *ptr;
  479. {
  480.     u size, *p;
  481.  
  482. /* Find the header again */
  483.  
  484.     p = (u *) ptr;
  485.     p-=1;
  486.  
  487. /* Update statistics */
  488.  
  489.     size = *p & MASK;
  490.     COUNT(large_alloc_stat, - (int) (size << 2));
  491.  
  492. /* Since this is about to become a hole, check memory before and after
  493.    for holes.  If they are holes, merge them with this one.
  494. */
  495.     if (is_next_free(p)) {
  496.         remove_from_free_list(next_large_block(p));
  497.         size += (*next_large_block(p) & MASK);
  498.         *p = (*p & PREV_BLOCK) | size;
  499.     }
  500.  
  501.     if (is_previous_free(p)) {
  502.         remove_from_free_list(previous_largeblock(p));
  503.         size += (*previous_largeblock(p) & MASK);
  504.         p = previous_largeblock(p);
  505.     }
  506.  
  507.     build_block(p, size);
  508.     add_to_free_list(p);
  509. }
  510.  
  511. void *realloc(p, size)
  512. char *p; unsigned size;
  513. {
  514.     unsigned *q,old_size;
  515.     char *t;
  516.     q = ((unsigned *) p)-1;
  517.     old_size = ((*q & MASK) -1) * SINT;
  518.  
  519.     if (old_size >= size)
  520.         return p;
  521.  
  522.     t = malloc(size);
  523.     if (t == 0) return (char *) 0;
  524.  
  525.     memcpy(t, p, old_size);
  526.     free(p);
  527.     return t;
  528. }
  529.  
  530. int resort_free_list() { return 0; }
  531.  
  532. #define d(str,stat) p(player, tprintf(str,stat.counter,stat.size))
  533. #define p notify
  534. #ifdef SLOW_STATISTICS
  535. void dump_malloc_data(player)
  536.     dbref player;
  537. {
  538. p(player, "TOTAL ALLOCATIONS  (all requests ever made)" );
  539. p(player, " Type               Count      Space (bytes)" );
  540. d(" large blocks:  %9d      %12ld", large_total_stat);
  541. d(" small blocks:  %9d      %12ld", small_total_stat);
  542. d(" sbrk requests:  %8d        %10ld (a)",sbrk_stat);
  543. if (large_free_chain.counter)
  544. p(player, tprintf(" large mallocs: %9d      average search length: %7.2f",
  545.           large_free_chain.counter,
  546.           (double) large_free_chain.size/large_free_chain.counter));
  547. p(player, "CURRENT USAGE");
  548. p(player, " Type               Count      Space (bytes)" );
  549. d(" large blocks:   %8d        %10ld (b)", large_alloc_stat);
  550. d(" large holes:    %8d        %10ld (c)", large_free_stat);
  551. d(" small chunks:   %8d        %10ld (d)", small_chunk_stat);
  552. d(" small blocks:   %8d        %10ld (e)", small_alloc_stat);
  553. d(" small holes:    %8d        %10ld (f)", small_free_stat);
  554. p(player, tprintf(" unused from current chunk       %10d (g)",
  555.           unused_size<<2));
  556. p(player, "NOTES");
  557. p(player, "  Small blocks are stored in small chunks, which are allocated as");
  558. p(player,"large blocks.  Therefore, the total large blocks allocated (b) plus");
  559. p(player,"the large free blocks (c) should equal total storage from sbrk (a).");
  560. p(player,"Similarly, (e) + (f) + (g) equals (d).  The total amount of storage");
  561. p(player,"wasted is (c) + (f) + (g); the amount allocated is (b) - (f) - (g).");
  562. }
  563. #endif
  564. #undef p
  565. #undef d
  566.  
  567. /*
  568.     Modified by Lars Pensj| (??)
  569.     calloc() is provided because some stdio packages uses it.
  570. */
  571. void *calloc(nelem, sizel)
  572. unsigned nelem, sizel;
  573. {
  574.     char *p;
  575.  
  576.     if (nelem == 0 || sizel == 0)
  577.         return 0;
  578.     p = malloc(nelem * sizel);
  579.     if (p == 0)
  580.         return 0;
  581.     (void) memset(p, 0, nelem * sizel);
  582.     return p;
  583. }
  584.  
  585. /*
  586.  * Functions below can be used to debug malloc.
  587.  */
  588.  
  589. #ifdef DEBUG
  590.  
  591. unsigned int memused() { return sbrk_stat.size; }
  592.  
  593. /*
  594.  * Verify that the free list is correct. The upper limit compared to
  595.  * is very machine dependant.
  596.  */
  597. verify_sfltable(player)
  598.     dbref player;
  599. {
  600.     u *p;
  601.     int i, j;
  602.     extern int end;
  603.  
  604.     if (!debugmalloc)
  605.     return;
  606.     if (unused_size > SMALL_CHUNK_SIZE / SINT) {
  607.       fprintf(stderr, "ERROR: free list.  SMALL_CHUNK/SINT < unused");
  608.       notify(player, "ERROR: free list.  SMALL_CHUNK/SINT < unused");
  609.     }
  610.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  611.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  612.         if (p < (u *)&end || p > (u *) 0xfffff) {
  613.         fprintf(stderr, "ERROR: free list. pointer out of range.");
  614.         notify(player, "ERROR: free list. pointer out of range.");
  615.         }
  616.         if (*p - 2 != i) {
  617.         fprintf(stderr, "ERROR: free list. pointer corrupt.");
  618.         notify(player, "ERROR: free list. pointer corrupt.");
  619.         }
  620.     }
  621.     if (p >= next_unused && p < next_unused + unused_size) {
  622.         notify(player, "ERROR: free list.  pointer in bad place.");
  623.         fprintf(stderr, "ERROR: free list.  pointer in bad place.");
  624.     }
  625.     }
  626.     p = free_list;
  627.     while (p) {
  628.     if (p >= next_unused && p < next_unused + unused_size) {
  629.         notify(player, "ERROR: free list.  pointer in bad place.");
  630.         fprintf(stderr, "ERROR: free list.  pointer in bad place.");
  631.     }
  632.     p = next_free_largeblock(p);
  633.     }
  634. }
  635.  
  636. verify_free(ptr)
  637.     u *ptr;
  638. {
  639.     u *p;
  640.     int i, j;
  641.  
  642.     if (!debugmalloc)
  643.     return;
  644.     for (i=0; i < SMALL_BLOCK_MAX; i++) {
  645.     for (j=0, p = sfltable[i]; p; p = * (u **) (p + 1), j++) {
  646.         if (*p - 2 != i)
  647.         fprintf(stderr, "ERROR: error in free list");
  648.         if (ptr >= p && ptr < p + *p)
  649.         fprintf(stderr, "ERROR: error in free list");
  650.         if (p >= ptr && p < ptr + *ptr)
  651.         fprintf(stderr, "ERROR: error in free list");
  652.         if (p >= next_unused && p < next_unused + unused_size)
  653.         fprintf(stderr, "ERROR: error in free list");
  654.     }
  655.     }
  656.  
  657.     p = free_list;
  658.     while (p) {
  659.     if (ptr >= p && ptr < p + (*p & MASK))
  660.         fprintf(stderr, "ERROR: error in free list");
  661.     if (p >= ptr && p < ptr + (*ptr & MASK))
  662.         fprintf(stderr, "ERROR: error in free list");
  663.     if (p >= next_unused && p < next_unused + unused_size)
  664.         fprintf(stderr, "ERROR: error in free list");
  665.     p = next_free_largeblock(p);
  666.     }
  667.     if (ptr >= next_unused && ptr < next_unused + unused_size)
  668.     fprintf(stderr, "ERROR: error in free list");
  669. }
  670. #endif /* DEBUG */
  671. #endif /* USE_SMALLOC */
  672.